package HelloAlgo.va;

/**
 * @author jing
 * @BelongsProject: JavaDataStructure
 * @CreateTime: 2025-03-08  20:28
 * @Description: 在不使用sqrt(x)函数的情况下，计算并返回 x 的平方根的整数部分。
 * 重点考察：二分法，牛顿迭代法
 * @Version: 1.0
 */
public class _005SqrtX {
    public static void main(String[] args) {
        System.out.println(binarySearch(25));
    }

    //二分法
    public static int binarySearch(int x) {
        int index = -1,l = 0, r = x;
        while(l <= r){
            int mid = l + (r - l) / 2;
            if(mid * mid <= x){
                index = mid;
                l = mid + 1;
            }else {
                r = mid - 1;
            }
        }
        return index;
    }
}
